import java.util.*;

/**
 * @Author Ap0stoL
 * @Description：
 */
public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /*
    遍历思路
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return ret;
        //System.out.print(root.val+" ");
        ret.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ret;
    }
    */
    //子问题
    /*public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        ret.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }*/

    // 中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(TreeNode root) {
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    public static int usedSize = 0;
    // 获取树中节点的个数
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        usedSize++;
        size(root.left);
        size(root.right);
        return usedSize;
    }

    public int size2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return  size2(root.left) + size2(root.right) + 1;
    }

    public static int leafSize = 0;
    public int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;
    }

    public int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
           return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)
                + getKLevelNodeCount(root.right,k-1);
    }

    /**
     * 时间复杂度：O(N)
     * @param root
     * @return
     */
    public  int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);

        return (leftH > rightH ? leftH :rightH) + 1;
    }

    public  int getHeight2(TreeNode root) {
        if(root == null) {
            return 0;
        }

        return (getHeight2(root.left) > getHeight2(root.right) ?
                getHeight2(root.left) :getHeight2(root.right)) + 1;
    }

    public TreeNode find(TreeNode root,int val) {
        if(root == null) return null;
        if(root.val == val) {
            return root;
        }
        TreeNode leftL = find(root.left,val);
        if(leftL != null) {
            return leftL;
        }
        TreeNode leftLR = find(root.right,val);
        if(leftLR != null) {
            return leftLR;
        }
        return null;
    }

    // 时间复杂度： O(min(m,n))
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        //一定是p 和 q 都不等于空！
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left)
                && isSameTree(p.right,q.right);
    }

    //时间复杂度：O(S*T)
    //每个s  都要和 t 判断是不是相同的！
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //时间复杂度：
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;

        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);

        return Math.abs(leftHight-rightHight) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    //O(n)
    public boolean isBalanced1(TreeNode root) {
        if(root == null) return true;
        return maxDepth(root) >= 0;
    }
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);

        if(leftH >= 0 && rightH >= 0 &&
                Math.abs(leftH-rightH) <= 1) {
            return Math.max(leftH,rightH) + 1;
        }else {
            return -1;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null ) {
            return false;
        }
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }






    
    //层序遍历
    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
       if(root != null) {
           queue.offer(root);
       }
       while (!queue.isEmpty()) {
           TreeNode top = queue.poll();
           System.out.print(top.val+" ");
           if(top.left != null) {
               queue.offer(top.left);
           }
           if(top.right != null) {
               queue.offer(top.right);
           }
       }

    }



    //返回每一层的元素,用链表套链表的方式连接起来
    /*public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//这一层节点的个数
            List<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode top = queue.poll();
                //System.out.print(top.val+" ");
                list.add(top.val);
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }*/



    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                return false;
            }
        }
        return true;
    }



    //最近公共祖先,利用栈来实现,下面的getpath是一起的
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        Stack<TreeNode> s1 = new Stack<>();
        getPath(root,p,s1);

        Stack<TreeNode> s2 = new Stack<>();
        getPath(root,q,s2);

        int size1 = s1.size();
        int size2 = s2.size();

        if(size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                s1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while (size != 0) {
                s2.pop();
                size--;
            }
        }
        //两个栈当中 的元素 是一样大小的
        while (!s1.empty() && !s2.empty()) {
            TreeNode tmp1 = s1.pop();
            TreeNode tmp2 = s2.pop();
            //这里比较的是地址,应为可能是同元素不同节点
            if(tmp1 == tmp2) {
                return tmp1;
            }
        }
        return null;
    }

    
    //在root这棵树当中 找到node这个节点上的位置

    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean ret = getPath(root.left,node,stack);
        if(ret == true) {
            return true;
        }

        boolean ret2 = getPath(root.right,node,stack);
        if(ret2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }






    //利用栈非递归前序遍历(利用栈)
    public void preOrderNor(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            //cur == null
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }


    //利用栈非递归中序遍历(利用栈)
    public void inOrderNor(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //cur == null
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }



    //利用栈非递归后序遍历(利用栈)
    public void postOrderNor(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev= null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //cur == null
            TreeNode top = stack.peek();//应为后序遍历是左右根所以不能直接取出来而是要判断有无右子树

            if(top.right == null || top.right == prev) {
                System.out.print(top.val+" ");
                prev = top;//记录下来当前的top已经被打印过了,不然会出现无线循环的情况
                stack.pop();
            }else {
                cur = top.right;
            }
        }
    }
}


